package leetcode.templates.searchs;

public class BinarySearch2 {
	int m, n;

	// 有序矩阵中第K
	public int findKthNumber(int m, int n, int k) {
		int ans = 0;
		int l = 1, r = m * n;
		this.m = m;
		this.n = n;
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			int num = this.count(m, 1, mid);
			if (num >= k) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return ans;
	}

	private int count(int x, int y, int ans) {
		if (x == 0 || y == n + 1) {
			return 0;
		}
		int cur = 0;
		int xy = x * y;
		if (ans >= xy) {
			cur += x + this.count(x, y + 1, ans);
		} else {
			cur += this.count(x - 1, y, ans);
		}
		return cur;
	}
}
